package listbyorder.access201_300.test218;

import java.util.*;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/23 22:16
 */
public class Solution1 {

    static class Node {
        int index;    // 位置
        int height;   // 高度
        boolean up;   // 是否想上增长

        public Node(int index, int height, boolean up) {
            this.index = index;
            this.height = height;
            this.up = up;
        }
    }

    public static List<List<Integer>> getSkyline(int[][] buildings) {
        int len = buildings.length;
        Node[] nodes = new Node[len * 2];
        for (int i = 0; i < len; i++) {
            nodes[i * 2] = new Node(buildings[i][0], buildings[i][2], true);
            nodes[i * 2 + 1] = new Node(buildings[i][1], buildings[i][2], false);
        }
        Arrays.sort(nodes, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if (o1.index != o2.index) {
                    return o1.index - o2.index;
                }
                if (o1.up != o2.up) {
                    return o1.up ? -1 : 1;
                }
                return 0;
            }
        });
        TreeMap<Integer, Integer> htMap = new TreeMap<>();
        TreeMap<Integer, Integer> pmMap = new TreeMap<>();
        for (int i = 0; i < nodes.length; i++) {
            int curH = nodes[i].height;
            if (nodes[i].up) {
                if (!htMap.containsKey(curH)) {
                    htMap.put(curH, 1);
                } else {
                    htMap.put(curH, htMap.get(curH) + 1);
                }
            } else {
                if (htMap.containsKey(curH)) {
                    if (htMap.get(curH) == 1) {
                        htMap.remove(curH);
                    } else {
                        htMap.put(curH, htMap.get(curH) - 1);
                    }
                }
            }
            if (htMap.isEmpty()) {
                pmMap.put(nodes[i].index, 0);   // 当前位置的最大高度设置为0
            } else {
                pmMap.put(nodes[i].index, htMap.lastKey());   // 放入当前map中最高的值
            }
        }
        // 遍历之后，根据两个treeMap获取论轮廓
        List<List<Integer>> ans = new ArrayList<>();
        int height = 0;
        for (Integer pos : pmMap.keySet()) {
            int curMaxHeight = pmMap.get(pos);
            if (curMaxHeight != height) {
                List<Integer> newRecord = new ArrayList<>();
                newRecord.add(pos);
                newRecord.add(curMaxHeight);
                ans.add(newRecord);
                height = curMaxHeight;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[][] arr = {{2, 9, 10}, {3, 7, 15}, {5, 12, 12}, {15, 20, 10}, {19, 24, 8}};

        List<List<Integer>> ans = getSkyline(arr);
        for (List<Integer> an : ans) {
            for (Integer num : an) {
                System.out.println(num);
            }
        }
    }
}
